#include <iostream>
#include <vector>
#include <unordered_map>
#include <list>
using namespace std;

/*
380. O(1) 时间插入、删除和获取随机元素
* 如何使可变数组实现O(1)的删除:
* 删除时，将删除的元素与最后一个元素交换，然后删除最后一个元素
*/
class RandomizedSet
{
    vector<int> v;
    unordered_map<int, int> m;

public:
    RandomizedSet()
    {
    }

    bool insert(int val)
    {
        if (m.count(val))
        {
            return false;
        }
        v.push_back(val);
        m[val] = v.size() - 1;
        return true;
    }

    bool remove(int val)
    {
        if (m.count(val))
        {
            int rmindex = m[val];
            m[v.back()] = rmindex;
            v[rmindex] = v.back();
            v.pop_back();
            m.erase(val);
            return true;
        }
        return false;
    }

    int getRandom()
    {
        return v[rand() % v.size()];
    }
};

int main()
{
    cout << "Code380" << endl;
    RandomizedSet randomizedSet;
    randomizedSet.insert(1);   // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
    randomizedSet.remove(2);   // 返回 false ，表示集合中不存在 2 。
    randomizedSet.insert(2);   // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
    randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
    randomizedSet.remove(1);   // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
    randomizedSet.insert(2);   // 2 已在集合中，所以返回 false 。
    randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
    return 0;
}